#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;


class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums.size()==0){
            return false;
        }
        if(nums.size()==1){
            return nums[0]==target;
        }
        //直接采用二分查找
        int left = 0;
        int right = nums.size()-1;
        //恢复nums数组的二段性
        while(left<right&&nums[0]==nums[right]){
            right--;
        }
        //找到index
        
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[0]>nums[mid]){
                right = mid-1;
            }
            else{
                left = mid+1;
            }
        }
        int index = right;
        return func(nums,0,index,target)||func(nums,index+1,nums.size()-1,target);

    }
    bool func(vector<int>& nums ,int i,int j,int target){
        while(i<=j){
            int mid = (i+j)/2;
            if(nums[mid]==target){
                return true;
            }
            else if(nums[mid]<target){
                i = mid+1;
            }
            else{
                j = mid-1;
            }
        }
        return false;
    }
};

int main(){
    Solution S;
    vector<int> nums = {1,0,1,1,1};
    cout<<S.search(nums,0)<<endl;
}